변 (그래프 이론)

무향 변은 방향성이 없는 변을 말한다. 즉, 두 정점을 연결하는 선이 특정 방향을 가지지 않는다. 무향 그래프에서 변은 두 정점 사이의 대칭적인 관계를 나타내며, 정점 u와 v를 연결하는 변은 (u, v) 또는 집합 {u, v}로 표기한다. 이 표기에서 (u, v)와 (v, u)는 동일한 변을 의미한다.

무향 변의 존재는 두 정점이 서로 인접함을 정의한다. 한 정점에 연결된 무향 변의 개수를 그 정점의 차수라고 한다. 무향 그래프에서 모든 정점의 차수를 합하면 변의 개수의 두 배가 된다는 것이 차수 합 정리이다. 이는 각 변이 두 정점의 차수에 각각 한 번씩 기여하기 때문이다.

무향 변으로만 구성된 그래프를 무향 그래프라고 하며, 소셜 네트워크에서의 친구 관계나 도로망에서의 양방통행 도로 등을 모델링하는 데 널리 사용된다. 또한 깊이 우선 탐색이나 너비 우선 탐색과 같은 기본적인 그래프 탐색 알고리즘은 대부분 무향 그래프를 기반으로 설명된다.

무향 그래프의 중요한 성질로 연결성을 들 수 있다. 무향 그래프에서 임의의 두 정점 사이에 경로가 존재하면 해당 그래프는 연결되었다고 한다. 이러한 연결성은 오일러 경로나 해밀턴 경로의 존재 여부를 판별하는 조건과 깊이 연관되어 있다.

유향 변은 방향이 있는 변을 의미한다. 유향 그래프에서 두 정점 사이의 연결 관계를 나타내며, 순서가 있는 쌍 (u, v)로 표기한다. 여기서 u는 변이 시작되는 정점(꼬리)이고, v는 변이 도착하는 정점(머리)이다. 이 방향성은 관계의 비대칭성을 모델링하는 데 핵심적이다. 예를 들어, 도로망에서 일방통행로나 인터넷에서의 웹페이지 하이퍼링크 방향을 표현할 수 있다.

무향 변과 달리 유향 변은 인접 관계가 방향에 따라 달라진다. 정점 u에서 v로의 유향 변이 존재하면, u는 v의 외부 이웃, v는 u의 내부 이웃이 된다. 이에 따라 각 정점의 차수는 진입차수와 진출차수로 구분된다. 진입차수는 해당 정점을 머리로 하는 변의 수이고, 진출차수는 해당 정점을 꼬리로 하는 변의 수이다.

유향 변을 사용하는 유향 그래프는 인접 행렬로 표현할 때 비대칭 행렬이 될 수 있다. 또한 깊이 우선 탐색이나 위상 정렬과 같은 많은 그래프 알고리즘이 방향성에 기반하여 동작한다. 최단 경로 문제를 푸는 다익스트라 알고리즘이나 벨만-포드 알고리즘도 유향 그래프에 적용 가능하다.

가중 변은 각 변에 숫자 값인 가중치가 할당된 변을 말한다. 이 가중치는 연결의 강도, 비용, 거리, 용량, 시간 등 다양한 의미를 가질 수 있으며, 그래프가 모델링하는 실제 문제에 따라 그 의미가 달라진다. 예를 들어, 도로망에서 두 도시를 연결하는 도로의 길이, 통신망에서 두 노드 간의 대역폭, 소셜 네트워크에서 두 사람 간의 친밀도 등을 가중치로 표현할 수 있다. 이러한 가중치는 그래프를 분석하거나 알고리즘을 적용할 때 핵심적인 정보로 작용한다.

가중 그래프는 가중 변을 하나 이상 포함하는 그래프를 지칭하며, 무향 또는 유향 그래프 모두에 적용될 수 있다. 가중치의 존재는 최단 경로 문제나 최소 신장 트리 찾기와 같은 고전적인 그래프 문제의 정의와 해법을 근본적으로 바꾼다. 예를 들어, 가중치가 없는 그래프에서는 두 정점 사이의 최단 경로를 단순히 거쳐가는 변의 수가 가장 적은 경로로 정의하지만, 가중 그래프에서는 경로를 구성하는 모든 변의 가중치 합이 최소가 되는 경로를 찾는 문제로 확장된다.

가중 변은 그래프를 인접 행렬이나 인접 리스트로 표현할 때도 그 값이 함께 저장된다. 인접 행렬에서는 각 셀에 가중치 값을 저장하며, 두 정점이 연결되지 않은 경우에는 보통 0이나 무한대(∞)로 표시한다. 인접 리스트에서는 각 정점의 연결 목록에 (연결된 정점, 가중치) 쌍으로 정보를 저장한다. 이러한 데이터 구조는 가중치를 효율적으로 참조하고 활용하는 기반이 된다.

루프는 한 정점에서 출발하여 다시 그 자신으로 돌아오는 변을 의미한다. 즉, 두 끝점이 동일한 정점인 특수한 형태의 변이다. 무향 그래프에서 루프는 {v, v}와 같이 집합으로 표기할 수 있으며, 유향 그래프에서는 (v, v)와 같은 순서쌍으로 나타낼 수 있다.

루프는 차수 계산에 특별한 영향을 미친다. 무향 그래프에서 루프는 해당 정점의 차수에 2를 더한다. 이는 루프가 해당 정점에 연결된 두 개의 끝점을 제공하는 것으로 간주되기 때문이다. 이 규칙은 모든 정점의 차수 합이 변 수의 두 배라는 차수 합 정리를 유지하는 데 중요하다.

루프는 실제 세계의 관계를 모델링할 때 자기 참조나 자기 상호작용을 표현하는 데 사용될 수 있다. 예를 들어, 소셜 네트워크에서 자기 자신에게 메시지를 보내는 행위나, 회로 이론에서 커패시터의 한 단자가 자기 자신과 연결되는 경우를 생각할 수 있다. 그러나 많은 기본적인 그래프 이론 문제나 알고리즘에서는 단순 그래프를 가정하여 루프를 허용하지 않는 경우가 많다.

다중 변은 두 정점 사이에 여러 개의 변이 존재할 수 있는 그래프의 변 유형이다. 일반적인 단순 그래프에서는 두 정점 사이에 최대 하나의 변만 존재하지만, 다중 그래프에서는 동일한 두 정점 쌍을 연결하는 변이 둘 이상 허용된다. 이는 실제 세계의 복잡한 관계를 모델링할 때 유용하다. 예를 들어, 두 도시 사이에 여러 개의 서로 다른 항공편이나 도로가 존재하는 경우, 각각의 연결을 별도의 변으로 표현하기 위해 다중 변 개념이 사용된다.

다중 변을 포함하는 그래프를 표현할 때는 인접 행렬이나 인접 리스트 방식에 약간의 변형이 필요하다. 인접 행렬의 경우, 각 셀에 변의 개수를 정수로 기록하거나, 리스트를 저장하여 여러 개의 연결을 표시할 수 있다. 간선 리스트 방식은 다중 변을 가장 직관적으로 표현할 수 있는 방법 중 하나로, 각 변을 (시작 정점, 끝 정점)의 쌍으로 나열하면 되기 때문이다. 다중 변은 그래프의 차수 계산에도 영향을 미치는데, 한 정점에 연결된 모든 다중 변은 각각 차수에 포함된다.

다중 변은 그래프 이론의 여러 알고리즘과 문제에서 고려해야 할 요소가 된다. 예를 들어, 오일러 경로나 해밀턴 경로를 찾는 문제에서 다중 변의 존재는 경로의 가능성을 증가시킬 수 있다. 반면, 최단 경로 문제에서는 동일한 두 정점을 연결하는 여러 변 중 가장 비용이 낮은(가중치가 작은) 변만을 고려하는 방식으로 처리되기도 한다. 이처럼 다중 변은 그래프의 구조와 알고리즘의 복잡성에 직접적인 영향을 미치는 중요한 개념이다.

정점은 그래프 이론에서 그래프를 구성하는 가장 기본적인 요소이다. 점, 노드, 꼭짓점이라고도 불리며, 추상적인 대상이나 개체를 나타낸다. 예를 들어, 소셜 네트워크에서는 사람이, 교통망에서는 교차로나 역이, 컴퓨터 네트워크에서는 컴퓨터나 라우터가 정점으로 표현될 수 있다. 그래프는 이러한 정점들과 이들을 연결하는 변들의 집합으로 정의된다.

정점의 주요 특성 중 하나는 차수이다. 무향 그래프에서 한 정점의 차수는 그 정점에 연결된 변의 수를 의미한다. 유향 그래프에서는 진입차수와 진출차수로 나뉜다. 모든 정점의 차수를 합한 값은 그래프 내 변의 총 수와 밀접한 관계가 있으며, 이는 차수 합 정리로 설명된다. 이 정리에 따르면 무향 그래프에서 모든 정점의 차수 합은 변 수의 두 배와 같다.

정점들은 변을 통해 서로 인접할 수 있으며, 일련의 변과 정점을 따라 이동하는 것을 경로라고 한다. 정점의 연결 상태는 그래프의 전체적인 연결성을 결정하며, 모든 정점 쌍 사이에 경로가 존재하면 해당 그래프는 연결되었다고 한다. 또한, 오일러 경로나 해밀턴 경로와 같은 고전 문제들도 정점과 변의 특정 조건을 통해 정의된다.

그래프 이론에서 차수는 특정 정점에 연결된 변의 수를 의미한다. 무향 그래프에서 정점 v의 차수는 v에 인접한 변의 개수로 정의되며, 보통 deg(v)로 표기한다. 유향 그래프에서는 정점에 들어오는 변의 수를 진입 차수, 나가는 변의 수를 진출 차수로 구분하여 정의한다.

차수는 그래프의 구조를 분석하는 데 핵심적인 개념이다. 모든 정점의 차수를 합한 값은 변의 수에 2를 곱한 값과 같다는 차수 합 정리가 성립한다. 이는 각 변이 두 개의 정점에 기여하기 때문에 발생하는 기본 성질이다. 또한, 그래프 내에서 오일러 경로나 오일러 회로가 존재하기 위한 필요충분 조건은 차수의 홀짝성과 직접적으로 연관되어 있다.

차수는 그래프의 특성을 분류하는 데도 사용된다. 모든 정점의 차수가 같은 그래프를 정규 그래프라고 부른다. 특히, 차수가 0인 정점을 고립점, 차수가 1인 정점을 잎 정점이라고 한다. 이러한 개념들은 트리나 네트워크 분석에서 중요한 역할을 한다.

경로는 그래프 이론에서 연속된 변을 따라 이동하여 한 정점에서 다른 정점에 도달하는 방법을 설명하는 개념이다. 정점들의 순서열로 정의되며, 인접한 두 정점 사이에는 항상 변이 존재해야 한다. 경로의 길이는 경로를 구성하는 변의 수로 정의된다. 예를 들어, 정점 A, B, C가 있고 변 (A, B)와 (B, C)가 존재한다면, A-B-C는 길이가 2인 하나의 경로가 된다.

경로는 여러 기준에 따라 분류된다. 가장 기본적인 구분은 단순 경로와 단순하지 않은 경로이다. 단순 경로는 경로 상의 모든 정점이 서로 달라, 같은 정점을 두 번 이상 방문하지 않는 경로를 의미한다. 반면, 같은 정점을 반복하여 지나는 경로는 단순하지 않은 경로로 본다. 또한, 시작 정점과 끝 정점이 같은 경로를 특히 사이클 또는 회로라고 부른다.

경로는 그래프의 연결성을 판단하는 핵심 도구이다. 두 정점 사이에 경로가 존재하면 두 정점은 연결되어 있다고 말한다. 또한, 최단 경로 문제나 탐색 알고리즘과 같은 중요한 알고리즘 문제들은 모두 정점들 사이의 특정 경로를 찾는 것을 목표로 한다.

변은 그래프의 연결성을 정의하는 핵심 요소이다. 그래프가 연결되었다는 것은 임의의 두 정점 사이에 변으로 이루어진 경로가 존재함을 의미하며, 이 연결성은 변의 존재 유무와 배치에 의해 결정된다. 변이 하나도 없는 그래프는 모든 정점이 고립되어 있으며, 변이 충분히 많아 모든 정점 쌍을 직접 연결하면 완전 그래프가 된다.

연결성의 강도를 구분하는 개념도 변을 통해 정의된다. 예를 들어, 절단점이나 절단선은 그래프에서 제거했을 때 연결된 요소의 수가 증가하게 만드는 정점이나 변을 지칭한다. 특히 절단선은 해당 변을 제거하면 그래프가 두 개 이상의 연결 요소로 분리되는 변을 의미한다. k-연결 그래프와 같은 개념은 그래프의 내결함성이나 신뢰성을 수치화할 때 변의 역할을 고려하여 정의된다.

변의 관점에서 그래프의 구조를 분석하는 것은 네트워크의 견고성, 정보 전달 효율성, 장애 대응 능력을 평가하는 데 필수적이다. 통신 네트워크에서 특정 회선(변)의 고장이 전체 네트워크의 단절로 이어지는지 판단하거나, 교통망에서 다리(변) 하나가 무너졌을 때 대체 경로가 존재하는지 분석하는 데 연결성에 대한 이해가 적용된다.

인접 행렬은 그래프의 정점들 사이의 연결 관계를 정방형 행렬로 표현하는 방법이다. 행렬의 행과 열은 각각 그래프의 정점에 대응되며, 행렬의 원소는 두 정점 사이에 변이 존재하는지 여부 또는 그 가중치를 나타낸다.

무향 그래프의 경우, 정점 i와 정점 j가 연결되어 있으면 행렬의 (i, j)와 (j, i) 위치에 1을 기록한다. 연결되어 있지 않으면 0을 기록한다. 이로 인해 무향 그래프의 인접 행렬은 주대각선을 기준으로 대칭이 된다. 유향 그래프에서는 방향성을 고려하여, 정점 i에서 정점 j로 향하는 변이 존재할 때만 (i, j) 위치에 1을 기록한다.

인접 행렬 표현법의 장점은 두 정점 사이의 연결 여부를 상수 시간(O(1))에 확인할 수 있다는 점이다. 그러나 정점의 수를 V, 변의 수를 E라고 할 때, 행렬 자체는 V^2 크기의 공간을 차지하므로, 변의 수가 적은 희소 그래프에서는 공간 효율이 떨어진다. 또한 한 정점에 연결된 모든 이웃 정점을 찾기 위해서는 해당 행 전체를 탐색해야 하므로 O(V)의 시간이 소요된다.

이 방법은 그래프의 연결성을 파악하거나 행렬 곱셈을 이용해 정점 사이의 경로 수를 계산하는 등 수학적 분석에 유용하게 활용된다. 반면, 인접 리스트나 간선 리스트는 공간 효율성이나 특정 연산에 더 적합한 다른 표현 방식이다.

인접 리스트는 그래프를 표현하는 방법 중 하나로, 각 정점에 연결된 모든 변의 정보를 리스트 형태로 저장하는 방식이다. 인접 행렬이 모든 정점 쌍에 대한 연결 여부를 행렬로 표현하는 것과 달리, 인접 리스트는 실제로 존재하는 연결 관계만을 저장하기 때문에 희소 그래프를 표현할 때 공간 효율이 높다.

구현 방식은 각 정점마다 하나의 리스트를 할당하고, 그 리스트에 해당 정점과 직접 연결된 다른 정점들을 기록한다. 예를 들어, 무향 그래프에서 정점 A가 정점 B와 C와 연결되어 있다면, 정점 A의 인접 리스트에는 B와 C가 저장된다. 유향 그래프의 경우, 리스트에 저장되는 정점은 보통 해당 변의 머리 정점을 의미하며, 꼬리 정점의 리스트에 추가된다.

인접 리스트 표현법의 주요 연산 성능은 다음과 같다. 특정 변의 존재 여부를 확인하려면 한 정점의 리스트를 선형 검색해야 하므로, 최악의 경우 해당 정점의 차수에 비례하는 시간이 소요될 수 있다. 반면, 한 정점에 인접한 모든 정점을 나열하는 작업은 매우 효율적이다. 이 특성 때문에 깊이 우선 탐색이나 너비 우선 탐색과 같이 인접 정점들을 순회하는 그래프 탐색 알고리즘에서 널리 사용된다.

따라서 변의 수가 정점 수에 비해 상대적으로 적은 희소 그래프나, 인접 정점 순회가 빈번한 알고리즘 구현에 인접 리스트 표현이 적합하다.

간선 리스트는 그래프를 표현하는 가장 직관적인 방법 중 하나로, 모든 변을 명시적으로 나열한 자료구조이다. 각 변은 연결하는 두 정점의 쌍으로 저장되며, 무향 그래프의 경우 순서가 없고 유향 그래프의 경우 순서가 중요하다.

이 표현 방식은 구현이 단순하고, 모든 변을 직접 저장하기 때문에 변 자체를 순회하거나 추가/삭제하는 작업이 비교적 간단하다. 또한 가중치가 있는 가중 변의 경우, 각 변에 추가 정보를 쉽게 부여할 수 있다. 그러나 특정 정점에 인접한 모든 변을 찾거나 두 정점 사이에 변이 존재하는지 확인하는 연산은 리스트 전체를 탐색해야 하므로 비효율적일 수 있다.

따라서 간선 리스트는 변의 수에 비해 정점의 수가 매우 많거나, 밀집 그래프가 아닌 희소 그래프에서, 혹은 크루스칼 알고리즘과 같이 모든 변을 정렬하여 처리하는 알고리즘에서 주로 활용된다. 이는 인접 행렬이나 인접 리스트와 함께 그래프를 표현하는 기본적인 세 가지 방법을 구성한다.

변은 네트워크를 모델링하는 데 있어 핵심적인 구성 요소로 활용된다. 여기서 네트워크란 교통망, 통신망, 소셜 네트워크, 생물학적 네트워크 등 다양한 실세계의 연결 구조를 포괄한다. 이때 네트워크의 구성 요소(예: 사람, 컴퓨터, 도시)는 정점으로, 그들 사이의 관계(친구 관계, 데이터 연결, 도로)는 변으로 표현된다. 이러한 모델링을 통해 복잡한 시스템의 구조를 추상화하고 분석할 수 있다.

예를 들어, 소셜 네트워크 분석에서는 사람을 정점으로, 친구 관계나 메시지 교환과 같은 상호작용을 무향 변이나 유향 변으로 나타낸다. 교통 시스템에서는 교차로나 도시가 정점이 되고, 그 사이의 도로나 항로가 변이 된다. 특히 도로의 통행 시간이나 통신망의 대역폭과 같은 추가 정보를 고려해야 할 때는 가중 변을 사용하여 모델링한다.

네트워크 모델링에서 변의 유형은 분석 목적에 따라 결정된다. 방향성이 중요한 인터넷의 라우팅이나 SNS의 팔로우 관계를 모델링할 때는 유향 변이 사용된다. 반면, 전력망이나 철도망과 같이 물리적 연결 자체가 중요한 경우에는 무향 변이 더 적합하다. 또한, 항공편 네트워크에서 두 공항 사이에 여러 항공사가 운항하는 경우와 같이 중복 연결을 표현해야 할 때는 다중 변이 활용되기도 한다.

이렇게 그래프 이론의 변을 통해 네트워크를 수학적으로 표현함으로써, 네트워크 흐름, 군집 분석, 중심성 분석과 같은 다양한 분석 기법을 적용할 수 있게 된다. 이는 시스템의 취약점을 찾거나, 정보 전파 경로를 예측하거나, 효율적인 자원 배분 방안을 모색하는 데 기여한다.

탐색 알고리즘은 그래프의 모든 정점과 변을 체계적으로 방문하기 위한 절차이다. 이 알고리즘들은 그래프의 구조를 이해하고, 특정 정점을 찾거나, 연결 요소를 확인하는 데 핵심적인 역할을 한다. 대표적인 두 가지 방법은 깊이 우선 탐색과 너비 우선 탐색이다.

깊이 우선 탐색은 한 정점에서 시작하여 가능한 한 깊숙이 탐색을 진행한 후, 더 이상 나아갈 수 없으면 되돌아와 다른 경로를 탐색하는 방식이다. 이 방법은 스택 자료구조나 재귀를 사용하여 구현된다. 깊이 우선 탐색은 그래프에서 사이클을 발견하거나, 위상 정렬을 수행하는 데 유용하게 활용된다.

너비 우선 탐색은 시작 정점에서 가까운 정점들부터 차례대로 방문하는 방식이다. 큐 자료구조를 사용하여 구현되며, 시작점으로부터의 최단 경로를 찾는 문제에 효과적이다. 이 알고리즘은 네트워크 분석에서 두 노드 사이의 최소 홉 수를 계산하거나, 웹 크롤러가 페이지를 수집하는 방식 등에 응용된다.

이 두 기본 탐색 알고리즘은 더 복잡한 그래프 알고리즘의 기초를 형성한다. 예를 들어, 다익스트라 알고리즘이나 A* 알고리즘 같은 최단 경로 알고리즘은 너비 우선 탐색의 개념을 확장한 것이다. 또한, 연결 요소를 찾거나 이분 그래프 판별 등 다양한 그래프 문제 해결의 첫 단계로 탐색 알고리즘이 널리 사용된다.

최단 경로 문제는 가중치가 부여된 그래프에서 한 정점에서 다른 정점까지 도달하는 데 드는 비용(가중치의 합)이 가장 작은 경로를 찾는 문제이다. 여기서 비용은 거리, 시간, 비용 등 다양한 척도로 해석될 수 있으며, 이 문제는 그래프 이론과 알고리즘 분야에서 매우 중요한 주제로 다뤄진다. 문제의 유형은 출발점과 도착점이 한 쌍으로 주어지는 단일 쌍 최단 경로, 하나의 출발점에서 그래프 내 모든 다른 정점까지의 최단 경로를 구하는 단일 출발 최단 경로, 그리고 모든 정점 쌍 사이의 최단 경로를 구하는 모든 쌍 최단 경로 문제 등으로 나눌 수 있다.

이 문제를 해결하는 대표적인 알고리즘으로는 다익스트라 알고리즘과 벨만-포드 알고리즘이 있다. 다익스트라 알고리즘은 모든 변의 가중치가 음수가 아닐 때 단일 출발 최단 경로를 효율적으로 찾으며, 우선순위 큐를 사용해 구현된다. 반면 벨만-포드 알고리즘은 가중치가 음수인 변이 존재할 경우에도 사용할 수 있으며, 음수 가중치 순환이 존재하는지 감지하는 기능도 갖추고 있다. 모든 쌍 최단 경로 문제에는 플로이드-워셜 알고리즘이 널리 사용된다.

최단 경로 문제는 이론적인 중요성을 넘어 실생활에 광범위하게 응용된다. 대표적으로 내비게이션 시스템에서 최적 경로를 탐색하거나, 네트워크 라우팅 프로토콜에서 데이터 패킷의 전송 경로를 결정하며, 물류 및 운송 계획에서 비용을 최소화하는 배송 루트를 설계하는 데 활용된다. 또한 로봇 공학의 경로 계획이나 게임 인공지능의 이동 알고리즘에서도 핵심적인 역할을 한다.

신장 트리는 주어진 그래프의 모든 정점을 포함하면서 사이클이 없는 연결 그래프의 부분 그래프를 의미한다. 즉, 원본 그래프의 정점은 모두 유지하되, 최소한의 변만을 사용하여 모든 정점이 서로 연결되도록 만든 트리 구조이다. 신장 트리는 그래프가 연결되어 있을 때만 존재하며, 하나의 그래프에서 여러 개의 서로 다른 신장 트리를 가질 수 있다.

신장 트리의 주요 응용 분야는 통신 네트워크 설계, 회로 이론, 클러스터 분석 등이 있다. 특히 최소 신장 트리 문제는 네트워크의 모든 지점을 가장 낮은 비용으로 연결하는 방법을 찾는 데 활용된다. 대표적인 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 있으며, 이들은 탐욕 알고리즘 방식을 기반으로 한다.

신장 트리의 성질을 통해 그래프의 구조적 특징을 분석할 수 있다. 예를 들어, 어떤 그래프의 신장 트리가 존재한다는 것은 해당 그래프가 연결되어 있음을 의미한다. 또한 n개의 정점을 가진 연결 그래프의 신장 트리는 정확히 (n-1)개의 변을 가지며, 이는 모든 트리의 기본 성질과 일치한다.